package com.zh.note.huawei.onehundred.数大雁;

/**
 * @Author: zhanghuan
 * @date: 2023/8/26 19:51
 * @description: create it
 */

import java.util.*;

/**
 *
 * https://dream.blog.csdn.net/article/details/131057206
 * 思路：最小几只大雁在叫
 * 1. 从头取开始遍历的完整的quack
 * 2. 遍历字符串统计所有的这个quack中有几个q（t）放在list中
 * 3. 在统计全部的字符串中判断能满足这t个q对应数量的quack最小值
 * 4. 取list中值跟小于t的最小值比较
 * 6. 返回t or n
 */
public class Main {
    public static void main(String[] args) {
        // Scanner sc = new Scanner(System.in);
        // String sound = sc.nextLine();
        // String sound = "quackquack";
        String sound = "qaauucqcaa";
        Character[] soundType = {'q', 'u', 'a', 'c', 'k'};
        List<Character> record = new ArrayList<>(Arrays.asList(soundType));
        int value = count(sound, record);
        System.out.println(value);
    }

    //qququaauqccauqkkcauqqkcauqqkcaaukccakkkck  quackqquackuackqqqqquack
    public static int count(String sound, List<Character> record) {
        //1.先记录连续的quack算一次
        List<Integer> qList = new ArrayList<>();
        int count = 0;
        int index = 0;
        //统计满足条件的q值数量
        for (int i = 0; i < sound.length(); i++) {
            char ch = sound.charAt(i);
            if (ch == 'q') {
                count++;
            }

            Character targetCh = record.get(index);
            if (ch == targetCh) {
                if (index == 4) {
                    qList.add(count);
                    count = 0;
                    index = 0;
                    continue;
                }
                index++;
            }
        }
        if (qList.size() == 0) {
            return -1;
        }
        Map<Character, Integer> map = new HashMap<>();
        for (int i = 0; i < sound.length(); i++) {
            char key = sound.charAt(i);
            map.put(key, map.getOrDefault(key, 0) + 1);
        }
        List<Map.Entry<Character, Integer>> list = new ArrayList<>(map.entrySet());
        Collections.sort(list, Comparator.comparingInt(Map.Entry::getValue));
        //取 q u a c k最小值
        Map.Entry<Character, Integer> entry = list.get(1);
        int min = entry.getValue();
        Collections.sort(qList, (m, n) -> n - m);
        for (int i = 0; i < qList.size(); i++) {
            if (qList.get(i) <= min) {
                return (qList.get(i));
            }
        }
        return min;
    }

}